package com.leetcode;

/**
 * 200. 岛屿数量
 *
 * @author fy
 * @date 2022/3/28 10:09
 */
public class Solution200 {
    private int m, n;
    private final int[][] d = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private boolean[][] visited;

    public int numIslands(char[][] grid) {
        int count = 0;
        if (grid == null) {
            return count;
        }
        this.m = grid.length;
        if (this.m <= 0) {
            return count;
        }
        this.n = grid[0].length;

        this.visited = new boolean[this.m][this.n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                this.visited[i][j] = false;
            }
        }

        // 遍历每一个坐标点, 标记岛屿并flood fill
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!this.visited[i][j] && grid[i][j] == '1') {
                    count++;
                    this.dfs(grid, i, j);
                }

            }
        }

        return count;
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < this.m && y >= 0 && y < this.n;
    }

    /**
     * 从grid[startX][startY]位置开始, 进行Flood Fill
     *
     * @param grid
     * @param startX
     * @param startY
     */
    private void dfs(char[][] grid, int startX, int startY) {
        this.visited[startX][startY] = true;
        for (int i = 0; i < this.d.length; i++) {
            int newX = startX + this.d[i][0];
            int newY = startY + this.d[i][1];
            if (this.inArea(newX, newY) && !this.visited[newX][newY] && grid[newX][newY] == '1') {
                dfs(grid, newX, newY);
            }
        }
    }

}
